package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 层序遍历最好解决
import (
	"container/list"
	"math"
)

func isEvenOddTree(root *TreeNode) bool {
	d := list.New()
	d.PushBack(root)
	level := 0
	for d.Len() > 0 {
		n := d.Len()
		// 偶数
		if level%2 == 0 {
			minNUm := 0
			for i := 0; i < n; i++ {
				node := d.Remove(d.Front()).(*TreeNode)
				if node.Val%2 != 1 || node.Val <= minNUm {
					return false
				}
				minNUm = node.Val
				if node.Left != nil {
					d.PushBack(node.Left)
				}
				if node.Right != nil {
					d.PushBack(node.Right)
				}
			}
		} else {
			maxNUm := math.MaxInt32
			for i := 0; i < n; i++ {
				node := d.Remove(d.Front()).(*TreeNode)
				if node.Val%2 != 0 || node.Val >= maxNUm {
					return false
				}
				maxNUm = node.Val
				if node.Left != nil {
					d.PushBack(node.Left)
				}
				if node.Right != nil {
					d.PushBack(node.Right)
				}
			}
		}
		level += 1
	}
	return true
}

// 官方的解法更加简洁，代码结构好
func isEvenOddTree1(root *TreeNode) bool {
	q := []*TreeNode{root}
	for level := 0; len(q) > 0; level++ {
		prev := 0
		if level%2 == 1 {
			prev = math.MaxInt32
		}
		size := len(q)
		for _, node := range q {
			val := node.Val
			if val%2 == level%2 || level%2 == 0 && val <= prev || level%2 == 1 && val >= prev {
				return false
			}
			prev = val
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		q = q[size:]
	}
	return true
}
